#ifndef GRIDDER
#define GRIDDER

#include <cmath>
#include <vector>

#include "ParticleCollection.h"

typedef std::vector< std::vector< ParticleIter > > GridderCellT;

//A grid block contains a list of cells for iterating over.
struct GridBlock {
	std::vector< GridderCellT::iterator > cells;
};

//Container for storing and querying things in a grid.
//
//XXX Using particleIters right now which are references...try to perform a full copy to utilze better cacheing.
//XXX Test cacheing
class Gridder {
public:
    Gridder( unsigned int numCellsx, unsigned int numCellsy, const glm::vec2 & min, const glm::vec2 & max )
		: 
		mMin(min), 
		mMax(max)
	{
		mNumCells[0] = numCellsx; 
		mNumCells[1] = numCellsy;

		mCellWidth = (mMax - mMin).x / mNumCells[0];

		mHashTble.resize( numCellsx * numCellsy + 2 );

		ComputeRatio();

		//Default cached is -1
		mCachedGB = std::make_pair<int, GridBlock> (-1, GridBlock() );
	}

	unsigned int GetHashVal ( unsigned int cellx, unsigned int celly ){
		return cellx + celly * this->mNumCells[0];
	}

	void GetCells( float x, float y, unsigned int & cellx, unsigned int & celly ){
		cellx = std::min(std::max(std::floor( x * mRatio[0] ), 0.0f), (float)mNumCells[0]-1);
		celly = std::min(std::max(std::floor( y * mRatio[1] ), 0.0f), (float)mNumCells[1]-1);
	}


	unsigned int Insert ( ParticleIter & inVal ) {
		unsigned int cellx, celly;
		GetCells(inVal.cPos().x, inVal.cPos().y, cellx, celly);
		unsigned int hashVal = GetHashVal(cellx, celly);
		mHashTble[hashVal].push_back(inVal);
		return hashVal;
	}
	
	void Clear() {
		for (int i = 0; i < mHashTble.size(); ++i) { mHashTble[i].clear(); }
	}

	void DrawGrid(  ) {

		glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
		glBegin(GL_QUADS);
		for (unsigned int i = 0; i < mNumCells[0] ; ++i) {
			for (unsigned int j = 0; j < mNumCells[1] ; ++j) {
				unsigned int cellx, celly;
				GetCells(mMin.x +  i * mCellL[0], mMin.y + j * mCellL[1], cellx, celly);
				if (mHashTble[GetHashVal(cellx, celly)].size() != 0) {

					glVertex2f( mMin.x +  i * mCellL[0], mMin.y + j * mCellL[1] );
					glVertex2f( mMin.x + (i+1)*mCellL[0],mMin.y + j*mCellL[1] );
					glVertex2f( mMin.x + (i+1) * mCellL[0], mMin.y +(j+1) * mCellL[1] );
					glVertex2f( mMin.x + (i)*mCellL[0],mMin.y + (j+1)*mCellL[1]  );
				}
			}
		}
		glEnd();
		glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
	}

	//XXX - This inserts a new element when called.
	std::vector< ParticleIter >::iterator Begin( float x, float y ) {
		unsigned int cellx, celly;
		GetCells(x, y, cellx, celly);
		return mHashTble[GetHashVal(cellx, celly)].begin();
	}

	std::vector< ParticleIter >::iterator End( float x, float y ) {
		unsigned int cellx, celly;
		GetCells(x, y, cellx, celly);
		return mHashTble[GetHashVal(cellx, celly)].end();
	}

	GridBlock GetOccupiedCells() {
		GridBlock gb;
		for (GridderCellT::iterator it = mHashTble.begin();
			it != mHashTble.end();
			++it){
				if (it->size() > 0){
					gb.cells.push_back(it);
				}
		}

		return gb;
	}

	unsigned int Size ( float x, float y ) {
		unsigned int cellx, celly;
		GetCells(x, y, cellx, celly);
		return mHashTble[GetHashVal(cellx, celly)].size();
	}

	GridderCellT::const_iterator BeginTable() {
		return mHashTble.cbegin();
	}

	GridderCellT::const_iterator EndTable() {
		return mHashTble.cend();
	}

	void CacheGB( int hashVal, GridBlock & gb) {
		mCachedGB = std::make_pair< int, GridBlock > (hashVal, gb);
	}

	//XXX mCellWidht calculation should be different.

	//Gets a grid of cells guarenteed to be within rad
	//Only returns the boundaries.
	GridBlock GetNH ( float x, float y, float rad ) {

		GridBlock gb;
		unsigned int cellX, cellY;

		int incCntr[2] = {0,0};
		GridderCellT::iterator it;

		GetCells(x, y, cellX, cellY);
		incCntr[0] = x - (cellX * mCellWidth) > mCellWidth*0.5 ? 1 : -1;
		incCntr[1] = y - (cellY * mCellWidth) > mCellWidth*0.5 ? 1 : -1;

		for (int i = 0; i < 2; ++i){
			for (int j = 0; j < 2; ++j){
		
				GetCells(x + this->mCellWidth*(i*incCntr[0]), y + this->mCellWidth*(j*incCntr[1]), cellX, cellY);
				unsigned int hVal = GetHashVal(cellX, cellY);
				it = (mHashTble.begin() + hVal);
				bool doAdd = true;
				//Make sure it's not already there yet.
				for (int jb = 0; jb < gb.cells.size(); ++jb){
					if (gb.cells[jb] == it){
						doAdd = false;
					}
				}
				if (doAdd){
					gb.cells.push_back( mHashTble.begin()+hVal );
				}
				
			}
		}

		return gb;
	}

private:

	std::pair< int, GridBlock > mCachedGB;

	//Most math intensive part of this.
	void ComputeRatio() {
		glm::vec2 span = mMax-mMin;
		mRatio[0] = (float) mNumCells[0] / (span.x);
		mRatio[1] = (float) mNumCells[1] / (span.y);

		mCellL[0] = (span.x) / (float) mNumCells[0];
		mCellL[1] = (span.y) / (float) mNumCells[1];
	}

	//Width of each cell.
	float mRatio[2];
	glm::vec2 mMin, mMax;
	unsigned int mNumCells[2];
	glm::vec2 mCellL;
	float mCellWidth;

	//Stores the actual cells
	
	std::vector< std::vector< ParticleIter > > mHashTble;
	//std::map< int, std::vector< ParticleIter > > mHashTble;
};

#endif